220. 存在重复元素 III

Similar Question

没感觉到和哈希有什么关系

leading to the advanced question

Solution Tips

方案一: 暴力法

var containsNearbyAlmostDuplicate = function(nums, k, t) {
    // 排序之后, 两个滑动窗口感觉是比较好的处理方法, 再想想哈希表有没有合适的方案
    // 肯定不能排序呀, 所以只能是单个滑动窗口, 不断的判断, 窗口的指针不断的相撞又分离即可

    // 可以生成一个排序哈希映射索引, keys 是 val 升序, 然后比对存储的索引, 就是说排序的同时生成这样一个哈希表, 但是其实本质是和方法一一样的, 只不过滑动的窗口变成了哈希表上 val 滑动而已, 还是没想到特别适合哈希表的方法

    
    // let left = 0;
    // let right = 0 + k;

    // while (left < right && right < nums.length) {
    //     if (Math.abs(nums[left] - nums[right]) <= t) {
    //         return true;
    //     }

    //     if (left < right) {
    //         left++
    //     }
    //     else {
    //         right++
    //     }
    // }
    // 滑动窗口感觉漏元素了, 还是没有理解透彻, 还不如暴力法限制 j 为 i + K
    
    for (let i = 0; i < nums.length; i++) {
        const left = nums[i];
        for (let j = i + 1; j <= i + k; j++) {
            const right = nums[j];
            if (Math.abs(left - right) <= t) {
                return true;
            }
        }
    }

    return false;
};

let nums = [-3,3,-6], k = 2, t = 3
console.log(containsNearbyAlmostDuplicate(nums, k, t));

二叉搜索树 【JAVA 通过，JS 超时】

如果窗口中维护的元素是有序的，只需要用二分搜索检查条件二是否是满足的就可以了。利用自平衡二叉搜索树，可以在对数时间内通过 插入 和 删除 来对滑动窗口内元素排序。

方法一 真正的瓶颈 在于检查第二个条件是否满足需要扫描滑动窗口中所有的元素。因此我们需要考虑的是有没有比全扫描更好的方法。

如果窗口内的元素是有序的，那么用两次二分搜索就可以找到 x+t 和 x-t 这两个边界值了。

然而不幸的是，窗口中的元素是无序的。这里有一个初学者非常容易犯的错误，那就是将滑动窗口维护成一个有序的数组。虽然在有序数组中 搜索 只需要花费对数时间，但是为了让数组保持有序，我们不得不做插入和删除的操作，而这些操作是非常不高效的。想象一下，如果你有一个 k 大小的有序数组，当你插入一个新元素 x 的时候。虽然可以在 O(logk) 时间内找到这个元素应该插入的位置，但最后还是需要 O(k) 的时间来将 x 插入这个有序数组。因为必须得把当前元素应该插入的位置之后的所有元素往后移一位。当你要删除一个元素的时候也是同样的道理。在删除了下标为 i 的元素之后，还需要把下标 i 之后的所有元素往前移一位。因此，这种做法并不会比方法一更好。

为了能让算法的效率得到真正的提升，我们需要引入一个支持 插入，搜索，删除 操作的 动态 数据结构，那就是自平衡二叉搜索树。

下面给出整个算法的伪代码：

• 初始化一颗空的二叉搜索树 set
• 对于每个元素 x，遍历整个数组
  • 在 set 上查找大于等于 x 的最小的数，如果 s−x≤t 则返回 true
  • 在 set 上查找小于等于 x 的最大的数，如果 x−g≤t 则返回 true
  • 在 set 中插入 x
  • 如果树的大小超过了 k, 则移除最早加入树的那个数。
• 返回 false

  var containsNearbyAlmostDuplicate = function (nums, k, t) {
    const len = nums.length;
    const tree = new BinarySearchTree();
    for (let i = 0; i < len; i++) {
      const ceil = tree.ceiling(nums[i]);
      if (ceil != null && ceil <= nums[i] + t) return true;

      const floor = tree.floor(nums[i]);
      if (floor != null && nums[i] <= floor + t) return true;

      tree.insert(nums[i]);
      if (tree.size() > k) tree.remove(nums[i - k]);
    }
    return false;
  };
  let nums = [1, 5, 9, 1, 5, 9],
    k = 2,
    t = 3;
  console.log(containsNearbyDuplicate(nums, k));

桶

回到这个问题，我们尝试去解决的最大的问题在于：

1. 对于给定的元素 xx, 在窗口中是否有存在区间 [x-t, x+t] 内的元素？
2. 我们能在常量时间内完成以上判断嘛？

我们不妨把把每个元素当做一个人的生日来考虑一下吧。假设你是班上新来的一位学生，你的生日在 三月 的某一天，你想知道班上是否有人生日跟你生日在 t=30 天以内。在这里我们先假设每个月都是 30 天，很明显，我们只需要检查所有生日在 二月，三月，四月 的同学就可以了。

之所以能这么做的原因在于，我们知道每个人的生日都属于一个桶，我们把这个桶称作月份！每个桶所包含的区间范围都是 t，这能极大的简化我们的问题。很显然，任何不在同一个桶或相邻桶的两个元素之间的距离一定是大于 t 的。

我们把上面提到的桶的思想应用到这个问题里面来，我们设计一些桶，让他们分别包含区间 ..., [0,t], [t+1, 2t+1] ,..., 我们把桶来当做窗口，于是每次我们只需要检查 x 所属的那个桶和相邻桶中的元素就可以了。终于，我们可以 在常量时间解决在窗口中搜索的问题 了。

还有一件值得注意的事，这个问题和桶排序的不同之处在于每次我们的桶里只需要 包含最多一个元素 就可以了，因为如果任意一个桶中包含了两个元素，那么这也就是意味着这两个元素是 足够接近的 了，这时候我们就直接得到答案了。因此，我们只需使用一个标签为桶序号的散列表就可以了。

  var containsNearbyAlmostDuplicate = function (nums, k, t) {
    if (t < 0) return false;
    const map = {};
    // 防止0造成的infinity
    const bucketSize = t + 1;
    for (let i = 0; i < nums.length; i++) {
      const bucketID = getID(nums[i], bucketSize);
      if (
        map[bucketID] !== undefined &&
        Math.abs(nums[i] - map[bucketID]) <= t
      ) {
        return true;
      }
      if (
        map[bucketID - 1] !== undefined &&
        Math.abs(nums[i] - map[bucketID - 1]) <= t
      ) {
        return true;
      }
      if (
        map[bucketID + 1] !== undefined &&
        Math.abs(nums[i] - map[bucketID + 1]) <= t
      ) {
        return true;
      }
      map[bucketID] = nums[i];
      if (i > k - 1) {
        const removeID = getID(nums[i - k], bucketSize);
        map[removeID] = undefined;
      }
    }
    function getID(x, w) {
      return Math.floor(x / w);
    }
    return false;
  };